package 面试v1.字节;

import leetcodev1.链表.Solution;

public class LeetCode213 {

    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        //累加的
        return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }

    //动态规划
    //dp[i]=max(dp[i−2]+nums[i],dp[i−1])
    public int robRange(int[] nums, int start, int end) {
        int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);//选当前 或 不选当前
            first = temp;
        }
        return second;
    }

    int ret = Integer.MIN_VALUE;

    public int rob1(int[] nums) {
        int length = nums.length;
        boolean[] visited = new boolean[length];
        for (int i = 0; i < length; i++) {
            helper(nums, visited, length, i, 0);
        }
        return ret;
    }

    private void helper(int[] nums, boolean[] visited, int length, int index, int count) {
        if (index >= length) {
            ret = Math.max(ret, count);
            return;
        }

        int beforeIndex = (index - 1) == -1 ? length - 1 : index - 1;
        int nextIndex = (index + 1) == length ? 0 : index + 1;

        helper(nums, visited, length, index + 1, count);
        if (!visited[beforeIndex] && !visited[nextIndex]) {
            visited[index] = true;
            helper(nums, visited, length, index + 1, count + nums[index]);
            visited[index] = false;
        }

    }
}
